package tree;

/**
 * @author way
 * @create 2025-02-12 17:16
 */
public class _105_buildTree {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) return null;
        return build(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode build(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd) {
        if (preorderStart == preorderEnd) return null;

        int rootVal = preorder[preorderStart];
        TreeNode root = new TreeNode(rootVal);
        int middleIndex;
        for (middleIndex = inorderStart; middleIndex < inorderEnd; middleIndex++) {
            if (inorder[middleIndex] == rootVal) {
                break;
            }
        }
        root.left = build(preorder, preorderStart + 1, preorderStart + 1 + (middleIndex - inorderStart), inorder, inorderStart, middleIndex);
        root.right = build(preorder, preorderStart + 1 + (middleIndex - inorderStart), preorderEnd, inorder, middleIndex + 1, inorderEnd);
        return root;
    }
}
